#include <lcthw/list_algos.h>
#include <lcthw/dbg.h>

static inline List *List_merge(List *left, List *right, List_compare cmp)
{
	List *result = List_create();
	void *value = NULL;

	while(List_count(left) > 0 || List_count(right) > 0) {
		if(List_count(left) > 0 && List_count(right) > 0) {
			if(cmp(List_first(left), List_first(right)) <= 0) {
				value = List_shift(left);
			} else {
				value = List_shift(right);
			}

			List_push(result, value);
		} else if(List_count(left) > 0) {
			value = List_shift(left);
			List_push(result, value);
		} else if(List_count(right) > 0) {
			value = List_shift(right);
			List_push(result, value);
		}
	}

	return result;
}

List *List_merge_sort(List *list, List_compare cmp)
{
	if(List_count(list) <= 1) {
		return list;
	}

	List *left = List_create();
	List *right = List_create();
	int middle = List_count(list) / 2;

	LIST_FOREACH(list, first, next, cur) {
		if(middle > 0) {
			List_push(left, cur->value);
		} else {
			List_push(right, cur->value);
		}

		middle--;
	}

	List *sort_left = List_merge_sort(left, cmp);
	List *sort_right = List_merge_sort(right, cmp);

	if(sort_left != left) List_destroy(left);
	if(sort_right != right) List_destroy(right);

	return List_merge(sort_left, sort_right, cmp);
}
